#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;

template<class K>
class DefaultHashFunc{
public:
    size_t operator()(const K& key){
        return (size_t)key;
    }
};

//对于字符串类型专门使用特化
template<>
class DefaultHashFunc<string>{
public:
    size_t operator()(const string& str){
        size_t hash=0;
        for(auto e : str){
            hash*=131;
            hash+=e;
        }

        return hash;
    }
};


//闭散列--开放定址法
namespace open_address{
    //枚举位置状态
    enum STATE{
        EXIST,
        EMPTY,
        DELETE
    };

    //哈希数据封装
    template<class K,class V>
    class HashData{
    public:
        pair<K,V> _kv;
        STATE _state=EMPTY;
    };

    //哈希表封装
    template<class K,class V,class HashFunc=DefaultHashFunc<K>>
    class HashTable{
    public:

        HashTable(){
            _table.resize(10);
        }

        bool insert(const pair<K,V>& kv){
            //检查一下插入的值是否已经存在
            if(Find(kv.first)){
                return false;
            }

            //判断是否需要扩容
            //当负载因子大于0.7时扩容
            if((double)_n/(double)_table.size()>=0.7){
                //扩容大小为原来大小的二倍
                size_t newSize=_table.size()*2;
                //创建一个新的哈希表并扩容
                HashTable<K,V> newHT;
                newHT._table.resize(newSize);

                //遍历旧的哈希表，将数据从新映射到新的哈希表中的对应位置
                for(size_t i=0;i<_table.size();i++){
                    if(_table[i]._state==EXIST){
                        newHT.insert(_table[i]._kv);
                    }
                }

                //交换完数据后一定要交换两个表，将新表作为_table
                _table.swap(newHT._table);

            }
            //插入
            HashFunc hf;
            size_t hashi=hf(kv.first)%_table.size();

            //如果当前位置已经存在值，就到下一个位置中存放
            while(_table[hashi]._state==EXIST){
                hashi++;
                //当下标hashi增加到数组最大长度时，从新置为0继续查找空位置存放
                if(hashi==_table.size()){
                    hashi=0;
                }
            }

            //找到对应位置后存放插入的数据，同时将位置状态标价为存在
            _table[hashi]._kv=kv;
            _table[hashi]._state=EXIST;
            ++_n;
            return true;
        }

        HashData<K,V>* Find(const K& key){
            //先获取对应下标
            HashFunc hf;
            size_t hashi=hf(key)%_table.size();

            //如果位置状态不为空，就循环查找，遇到空就结束
            while(_table[hashi]._state==EXIST){
                if(_table[hashi]._kv.first==key){
                    return &_table[hashi];
                }
                else{
                    hashi++;
                    if(hashi==_table.size()){
                        hashi=0;
                    }
                }
            }

            return nullptr;
        }

        bool erase(const K& key){
            HashData<K,V>* ret=Find(key);
            //查找不为空将当前数据位置状态修改为删除，数据个数减一
            if(ret){
                ret->_state=DELETE;
                --_n;
                return true;
            }
            
            return false;
        }

    private:
        vector<HashData<K,V>> _table;
        size_t _n=0;
    };
};

//哈希桶
namespace Hash_bucket{
    //节点数据封装
    template<class T>
    class HashNode{
    public:
        //构造函数
        HashNode(const T& data)
        :_data(data)
        ,_next(nullptr)
        {}

        T _data;
        HashNode<T>* _next;
    };

    //前置声明
    template<class K,class T,class KeyOfT,class HashFunc>
    class HashTable;

    //哈希表迭代器封装
    template<class K,class T,class Ptr,class Ref,class KeyOfT,class HashFunc>
    class HashIterator{
    public:
        typedef HashNode<T> Node;
        //因为哈希表迭代器类需要使用哈希表类，所以要前置声明一下
        typedef HashIterator<K,T,Ptr,Ref,KeyOfT,HashFunc> self;
        typedef HashIterator<K,T,T*,T&,KeyOfT,HashFunc> Iterator;

        Node* _node;
        //这里要设置一个哈希表的指针
        const HashTable<K,T,KeyOfT,HashFunc>* _hashtable;

        HashIterator(Node* node,const HashTable<K,T,KeyOfT,HashFunc>* hashtable)
        :_node(node)
        ,_hashtable(hashtable)
        {}

        //如果类模板实例化出来的是普通迭代器，对于这个函数来说就是构造函数
        //如果类模板实例化出来的是const类型的迭代器，对于这个函数来说就是拷贝构造函数，将普通迭代器转换成const类型的迭代器
        HashIterator(const Iterator& hash)
        :_node(hash._node)
        ,_hashtable(hash._hashtable)
        {}

        Ref operator*(){
            return _node->_data;
        }

        Ptr operator->(){
            return &_node->_data;
        }

        bool operator!=(const self& s){
            return _node!=s._node;
        }

        self& operator++(){
            //如果当前节点的下一个节点不为空，直接返回下一个节点
            if(_node->_next){
                _node=_node->_next;
            }

            //如果当前节点的下一个节点为空，就查找下一个桶的位置，返回第一个节点
            else{
                HashFunc hf;
                KeyOfT kot;

                //先获取对应的下标位置
                size_t hashi=hf(kot(_node->_data))%_hashtable->_table.size();
                hashi++;
                //找到不为空的下一个桶
                while(hashi<_hashtable->_table.size()){
                    if(_hashtable->_table[hashi]){
                        _node=_hashtable->_table[hashi];
                        return *this;
                    }
                    else{
                        hashi++;
                    }
                }

                _node=nullptr;
            }

            return *this;
        }
    };

    //哈希表封装
    template<class K,class T,class KeyOfT,class HashFunc=DefaultHashFunc<K>>
    class HashTable{
        //将哈希表的迭代器类设置成友元类，这样就可以使用私有成员
        //template<class K,class T,class KeyOfT,class HashFunc>
        //friend class HashIterator;

        typedef HashNode<T> Node;
    public:
        //迭代器类命名重定义
        typedef HashIterator<K,T,T*,T&,KeyOfT,HashFunc> iterator;
        typedef HashIterator<K,T,const T*,const T&,KeyOfT,HashFunc> const_iterator;


        iterator begin(){
            for(size_t i=0;i<_table.size();i++){
                Node* cur=_table[i];

                //如果当前节点位置不为空，就是第一个起始位置，返回
                if(cur){
                    return iterator(cur,this);
                }
            }

            return iterator(nullptr,this);
        }

        iterator end(){
            return iterator(nullptr,this);
        }

        const_iterator begin()const {
            for(size_t i=0;i<_table.size();i++){
                Node* cur=_table[i];

                if(cur){
                    return const_iterator(cur,this);
                }
            }

            return const_iterator(nullptr,this);
        }

        const_iterator end()const{
            return const_iterator(nullptr,this);
        }

        //构造函数
        HashTable()
        {
            //开辟数组空间并初始化为空指针
            _table.resize(10,nullptr);
        }

        //析构函数
        ~HashTable(){
            for(size_t i=0;i<_table.size();i++){
                Node* cur=_table[i];

                while(cur){
                    Node* next=cur->_next;
                    delete cur;
                    cur=next;
                }

                _table[i]=nullptr;
            }
        }

        //插入函数
        pair<iterator,bool> Insert(const T& data){
            KeyOfT kot;
            //检查插入的值是否已经存在
            iterator it=Find(kot(data));
            //这里不能直接it不等于空，因为it是迭代器类型，要和end()相比较空
            if(it!=end()){
                return make_pair(it,false);
            }
            HashFunc hf;

            //判断是否需要扩容
            if(_n==_table.size()){
                //新的容量大小是原来容量的二倍
                size_t newSize=_table.size()*2;

                //创建一个新的哈希表并初始化
                vector<Node*> newHT;
                newHT.resize(newSize,nullptr);

                //遍历旧表，将旧表中的节点存放到新的哈希表中映射的位置
                for(size_t i=0;i<_table.size();i++){
                    Node* cur=_table[i];

                    while(cur){
                        Node* next=cur->_next;

                        size_t hashi=hf(kot(cur->_data))%newHT.size();

                        //头插到新表中
                        cur->_next=newHT[hashi];
                        newHT[hashi]=cur;

                        cur=next;
                    }

                    //将旧表对应的位置置为空指针
                    _table[i]=nullptr;
                }

                //最后交换两个哈希表
                _table.swap(newHT);
            }

            //获取哈希表中映射的位置下标
            size_t hashi=hf(kot(data))%_table.size();

            //头插
            Node* newnode=new Node(data);
            newnode->_next=_table[hashi];
            _table[hashi]=newnode;

            ++_n;
            return make_pair(iterator(newnode,this),true);
        }

        //查找函数
        iterator Find(const K& key){
            HashFunc hf;
            KeyOfT kot;
            //先获取查找值在表中的映射位置
            size_t hashi=hf(key)%_table.size();

            //从当前位置的链表中查找对应节点
            Node* cur=_table[hashi];

            while(cur){
                //找到返回对应节点
                if(kot(cur->_data)==key){
                    //这里不能直接返回cur,因为迭代器中有两个成员变量，还要用到该节点的哈希表，所以要传this指针
                    //iterator(cur,this)相当于使用构造函数构造一个迭代器
                    return iterator(cur,this);
                }
                //没找到沿着链表继续查找
                else{
                    cur=cur->_next;
                }
            }

            //没有找到返回空
            return iterator(nullptr,this);
        }

        //删除函数
        bool Erase(const K& key){
            HashFunc hf;
            KeyOfT kot;
            //先获取删除值在表中的映射位置
            size_t hashi=hf(key)%_table.size();

            //找到当前值对应位置的链表头节点，依次往后查找，同时设置一个父节点
            Node* parent=nullptr;
            Node* cur=_table[hashi];

            while(cur){
                //如果找到删除节点，将父节点的下一个节点连接成删除节点的下一个
                if(kot(cur->_data)==key){
                    //如果删除节点是头节点
                    if(parent==nullptr){
                        _table[hashi]=cur->_next;
                    }
                    else{
                        parent->_next=cur->_next;
                    }

                    //释放删除节点
                    delete cur;
                    cur=nullptr;

                    return true;
                }

                //没有找到沿着链表继续查找
                else{
                    parent=cur;
                    cur=cur->_next;
                }
            }

            //直到找到空节点结束  
            return false;
        }

        void Print(){
            for(size_t i=0;i<_table.size();i++){
                printf("[%d]",i);
                Node* cur=_table[i];

                while(cur){
                    //cout<<cur->_kv.first<<":"<<cur->_kv.second<<"->";
                    cur=cur->_next;
                }
                cout<<"NULL"<<endl;
            }
            cout<<endl;
        }

    //private:
        //哈希表中每个数据存储的是节点，节点之间可以相互连接，构成链表，相当于哈希桶
        vector<Node*> _table;
        size_t _n=0;
    };
};